package com.da.javatest.algorithm;

import java.util.Arrays;

/**
 * @author Mr.nobody
 * @Description 二分查找
 * @date 2020/9/5
 */
public class BinarySearch3 {

    // 二分查找，在有序数组中查找指定值，找到返回下标，否则返回-1
    public static int binarySearch(int[] sortedArr, int num) {
        if (null == sortedArr || sortedArr.length == 0) {
            return -1;
        }
        int left = 0;
        int right = sortedArr.length - 1;
        int mid = 0;
        while (left <= right) {
            // 等同于mid = (left + right) / 2;
            // 但是下面的表达式既速度快，还能避免left+right溢出
            mid = left + ((right - left) >> 1);
            if (sortedArr[mid] == num) {
                return mid;
            } else if (sortedArr[mid] > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    // 二分查找，在有序数组中查找大于等于指定值的最左的数，找到返回下标，否则返回-1
    // 例如数组[1, 2, 2, 5, 8, 10, 11, 11, 11, 20]，指定值为2，则返回下标1
    // 指定值为7，则返回下标为4；指定值为0，返回下标0；指定值为25，则返回下标-1
    public static int greaterEqualBinarySearch(int[] sortedArr, int num) {
        if (null == sortedArr || sortedArr.length == 0) {
            return -1;
        }
        int left = 0;
        int right = sortedArr.length - 1;
        int mid = 0;
        // 记录满足的最左下标
        int mostLeftIndex = -1;
        while (left <= right) {
            // 等同于mid = (left + right) / 2;
            // 但是下面的表达式既速度快，还能避免left+right溢出
            mid = left + ((right - left) >> 1);
            if (sortedArr[mid] >= num) {
                mostLeftIndex = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return mostLeftIndex;
    }

    // 二分查找，在有序数组中查找小于等于指定值的最右的数，找到返回下标，否则返回-1
    // 例如数组[1, 2, 2, 5, 8, 10, 11, 11, 11, 20]，指定值为2，则返回下标2
    // 指定值为7，则返回下标为3；指定值为0，返回下标-1；指定值为25，则返回下标9
    public static int lessEqualBinarySearch(int[] sortedArr, int num) {
        if (null == sortedArr || sortedArr.length == 0) {
            return -1;
        }
        int left = 0;
        int right = sortedArr.length - 1;
        int mid = 0;
        // 记录满足的最右下标
        int mostRightIndex = -1;
        while (left <= right) {
            // 等同于mid = (left + right) / 2;
            // 但是下面的表达式既速度快，还能避免left+right溢出
            mid = left + ((right - left) >> 1);
            if (sortedArr[mid] <= num) {
                mostRightIndex = mid;
                left = mid + 1;
            } else {
                right = mid - 1;

            }
        }
        return mostRightIndex;
    }

    // 二分查找，在数组中(不一定要有序)查找局部最小数(随便一个就可以)，找到返回下标，否则返回-1
    // 何为局部最小值，当某一个位置i的数，只要小于等于i-1和i+1位置的数时，即i位置的数就是局部最小值
    // 如果不存在i-1或i+1位置，就不需要比较，例如0位置的数只需要小于等于1位置的数即可；
    // n-1位置的数只需要小于等于n-2位置的数即可;
    public static int localMinBinarySearch(int[] arr) {
        if (null == arr || arr.length == 0) {
            return -1;
        }
        if (arr.length == 1 || arr[0] <= arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] <= arr[arr.length - 2]) {
            return arr.length - 1;
        }

        // 既然数组头部和尾部都不满足局部最小值，那肯定整个数据区间是↘...↗走势
        // 则可以从中间切入，局部最小肯定在中间，左区间或者右区间存在，
        // 按此逻辑进行二分查找下去即可
        int left = 0;
        int right = arr.length - 1;
        int mid = 0;
        while (left <= right) {
            // 等同于mid = (left + right) / 2;
            // 但是下面的表达式既速度快，还能避免left+right溢出
            mid = left + ((right - left) >> 1);
            if (arr[mid - 1] >= arr[mid] && arr[mid] <= arr[mid + 1]) {
                // 既小于等于左边，又小于等于右边，满足局部最小值
                return mid;
            } else if (arr[mid - 1] < arr[mid]) {
                // 大于左边，则左边是↘...↗走势，那肯定在左边区间一定存在局部最小值
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                // 大于右边，则右边是是↘...↗走势，那肯定在右边区间一定存在局部最小值
                left = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 5, 8, 10, 11, 11, 11, 20};
        int num = 2;
        System.out.print("有序数组：");
        Arrays.stream(arr).forEach(e -> System.out.print(e + " "));
        System.out.println();
        System.out.println("待查找数：" + num);
        System.out.println("查找的下标：" + BinarySearch3.binarySearch(arr, num));

        System.out.println("----------------------------------------");

        System.out.println("大于等于的数：" + 2 + "，最左下标为："
            + BinarySearch3.greaterEqualBinarySearch(arr, 2));
        System.out.println("大于等于的数：" + 7 + "，最左下标为："
            + BinarySearch3.greaterEqualBinarySearch(arr, 7));
        System.out.println("大于等于的数：" + 0 + "，最左下标为："
            + BinarySearch3.greaterEqualBinarySearch(arr, 0));
        System.out.println("大于等于的数：" + 25 + "，最左下标为："
            + BinarySearch3.greaterEqualBinarySearch(arr, 25));

        System.out.println("----------------------------------------");

        System.out.println("小于等于的数：" + 2 + "，最右下标为："
            + BinarySearch3.lessEqualBinarySearch(arr, 2));
        System.out.println("小于等于的数：" + 7 + "，最右下标为："
            + BinarySearch3.lessEqualBinarySearch(arr, 7));
        System.out.println("小于等于的数：" + 0 + "，最右下标为："
            + BinarySearch3.lessEqualBinarySearch(arr, 0));
        System.out.println("小于等于的数：" + 25 + "，最右下标为："
            + BinarySearch3.lessEqualBinarySearch(arr, 25));

        System.out.println("----------------------------------------");
        int[] arr1 = {1, 2, 2, 10, 8, 4, 2, 11, 7, 20};
        System.out.print("数组：");
        Arrays.stream(arr1).forEach(e -> System.out.print(e + " "));
        System.out.println("，局部最小值下标：" + BinarySearch3.localMinBinarySearch(arr1));

        int[] arr2 = {4, 2, 2, 10, 8, 4, 2, 11, 7, 5};
        System.out.print("数组：");
        Arrays.stream(arr2).forEach(e -> System.out.print(e + " "));
        System.out.println("，局部最小值下标：" + BinarySearch3.localMinBinarySearch(arr2));

        int[] arr3 = {7, 2, 2, 10, 8, 4, 2, 11, 7, 20};
        System.out.print("数组：");
        Arrays.stream(arr3).forEach(e -> System.out.print(e + " "));
        System.out.println("，局部最小值下标：" + BinarySearch3.localMinBinarySearch(arr3));

        int[] arr4 = {3, 2, 4, 10, 8, 6, 7, 11, 7, 10};
        System.out.print("数组：");
        Arrays.stream(arr4).forEach(e -> System.out.print(e + " "));
        System.out.println("，局部最小值下标：" + BinarySearch3.localMinBinarySearch(arr4));
    }

}
